﻿#include"head.h"

//简便输入
void GetChar(char* ch) {scanf_s("%c", ch);}

//结点构造
tn CreateNode(char data) {
	tn newnode = (tn)malloc(sizeof(TN));
	newnode->data = data;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

//结点插入
void Insert(tn* root, char data) {
	*root = CreateNode(data);
}

//先序建立二叉树
void preCreate(tn* root) {
	char ch; GetChar(&ch);
	if (ch == ' ') {*root = NULL;}
	else {
		*root = CreateNode(ch);
		preCreate(&(*root)->left);
		preCreate(&(*root)->right);
	}
}

//先序遍历二叉树
void preTraversal(tn* root) {
	if (*root != NULL) {
		printf("%c", (*root)->data);
		preTraversal(&(*root)->left);
		preTraversal(&(*root)->right);
	}
}
//中序遍历
void inTraversal(tn* root) {
	if (*root != NULL) {
		inTraversal(&(*root)->left);
		printf("%c", (*root)->data);
		inTraversal(&(*root)->right);
	}
}
//后序遍历
void postTraversal(tn* root) {
	if (*root != NULL) {
		postTraversal(&(*root)->left);
		postTraversal(&(*root)->right);
		printf("%c", (*root)->data);
	}
}
//层序遍历
void levelTraversal(tn* root) {
	if (*root == NULL) { return; }
	tn queue[100];
	int front = 0, rear = 0;
	queue[rear++] = *root;
	while (front < rear) {
		tn theout = queue[front++];
		printf("%c", theout->data);
		if (theout->left != NULL) { queue[rear++] = theout->left; }
		if (theout->right != NULL) { queue[rear++] = theout->right; }
	}
}

//求二叉树深度
int CountDepth(tn root) {
	if (root == NULL) { return 0; }
	int l = CountDepth(root->left);
	int r = CountDepth(root->right);
	return (l > r ? l : r) + 1;
}
//求二叉树结点数
int CountNode(tn root) {
	if (root == NULL) { return 0; }
	int l = CountNode(root->left);
	int r = CountNode(root->right);
	return l + r + 1;
}
//求二叉树叶子数
int Countleaves(tn root) {
	if (root == NULL) { return 0; }
	if ((root)->left == NULL && (root)->right == NULL) { return 1; }
	int l = Countleaves(root->left);
	int r = Countleaves(root->right);
	return l + r;
}

//将二叉树每个结点左右子树交换
void Change(tn* root) {
	if (*root != NULL) {
		Change(&(*root)->left);
		Change(&(*root)->right);
		tn assist;
		assist = (*root)->left;
		(*root)->left = (*root)->right;
		(*root)->right = assist;
	}
}
//交换结果展示
void ShowChange(tn* root) {
	Change(&(*root));
	printf("将二叉树每个结点左右子树交换后得到：\n");
	printf("先序遍历结果："); preTraversal(&(*root)); printf("\n");
	printf("中序遍历结果："); inTraversal(&(*root)); printf("\n");
}

//非递归先序遍历
void Non_recursivePre_orderTraversal(tn root) {
	if (root == NULL) return;
	tn stack[100];
	int top = -1;
	stack[++top] = root;
	while (top >= 0) {
		tn node = stack[top--];
		printf("%c",node->data);
		if (node->right != NULL) {
			stack[++top] = node->right;
		}
		if (node->left != NULL) {
			stack[++top] = node->left;
		}
	}
	printf("\n");
}